const tree = require('./binTree')

const inorder = (root) => {
    if (!root) return
    inorder(root.left)  // 1
    console.log(root.val)  // 2
    inorder(root.right)  // 3
}

// 非递归方法，使用栈来模拟递归
const inorder1 = (root) => {
    if (!root) return []
    const stack = []
    let p = root
    // 1. 先模拟inorder(root.left)，从根节点开始将左子树推入栈中
    while(stack.length || p) {
        while(p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        console.log(n.val)  // 2. 访问节点
        p = n.right // 3. 遍历右节点
    }
}

inorder(tree)  // 4 2 5 1 6 3 7
inorder1(tree)  // 4 2 5 1 6 3 7